package com.leetcode.algorithm.y22.m06;

/**
 * 213. 打家劫舍 II
 * 
 * https://leetcode.cn/problems/house-robber-ii/
 * 
 * @author jie.deng
 *
 */
class Question0213Solution01 {

	public int rob(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return nums[0];
		}
		return Math.max(robRange(nums, 0, len-2), robRange(nums, 1, len-1));
	}

	private int robRange(int[] nums, int beginIdx, int endIdx) {
		// DP状态定义
		int[][] dp = new int[nums.length][2];

		// DP状态初始化
		// 不闯入i号房屋能够偷窃到的最高金额
		// 闯入i号房屋能够偷窃到的最高金额
		dp[beginIdx][0] = 0;
		dp[beginIdx][1] = nums[beginIdx];

		// 状态转移方程：
		for (int i = beginIdx + 1; i <= endIdx; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = dp[i - 1][0] + nums[i];
		}

		return Math.max(dp[endIdx][0], dp[endIdx][1]);
	}

}